import java.util.ArrayList;
import java.util.List;

public class FindMedianSortedArrays {

    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int l = 0;
        int r = 0;
        int n = nums1.length;
        int m = nums2.length;
        int temp = 0;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < (m + n) / 2; i++) {
            if (l < n && (r >= m || nums1[l] < nums2[r])) {
                temp = nums1[l];
                list.add(temp);
                l++;
            } else {
                temp = nums2[r];
                list.add(temp);
                r++;
            }
        }
        if ((m + n) % 2 != 0) return temp;
        return ((double) temp + list.get(list.size() - 2)) / 2;
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
        int m = nums1.length;
        int n = nums2.length;
        int l = 0;
        int r= m;
        int target = (m + n + 1) / 2;
        while (l < r) {
            int i = (l + r) / 2;
            int j = target - i;
            if (nums2[j -1] > nums1[i]) {
                l = i + 1;
            } else r = i;
        }
        int i = l;
        int j = target - i;
        int num1l = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int num1r = i == m ? Integer.MAX_VALUE : nums1[i];
        int num2l = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int num2r = j == n ? Integer.MAX_VALUE : nums2[j];
        if ((m + n) % 2 != 0) return Math.max(num1l, num2l);
        return (double) (Math.max(num1l, num2l) + Math.min(num1r, num2r)) / 2;
    }
}
